/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package gblend.largegraph.graphdivide;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.openide.util.Exceptions;

/**
 *
 * @author HO HOANG HUNG
 */
public class GraphDivide {

    //Threshold for number of vertices.
    private static int threshold, numpart;
    private static String resFolder;
    //Use for bordergraph ids.
    public static int idpower;
    private static Vector<Integer>[][] partitioned = null;
    private static HashMap<Integer, BorderGraph> borders = new HashMap<Integer, BorderGraph>();
    //For connectivity graph
    private static HashMap<Integer, HashSet<Integer>> conngrph = new HashMap<Integer, HashSet<Integer>>();
    private static int[] partvertex = null;

    public static int getVThreshold() {
        return threshold;
    }

    public static void setVThreshold(int newth) {
        if (newth > 0) {
            threshold = newth;
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        setVThreshold(50);
        System.out.print("FileName?");
        String fname = sc.next();
        divide(fname);
//        constructBorderGraph(fname);
    }

    public static boolean divide(String fileName) {
        String folderN = fileName.replace('.', '_');
        File folder = new File(folderN + "Folder");
        boolean res = folder.mkdirs();
        res = folder.mkdir();
        if (folder.exists() || res) {
            resFolder = new String(folderN + "Folder");
            divideGraph(fileName);
            return true;
        } else {
            System.out.println("divide return false");
            return res;
        }
    }

    private static boolean divideGraph(String fileName) {
        File fl = new File(fileName);
        if (fl.exists()) {
            int numvertex = getNumOfVertex1(fl);
            System.out.println("Graph has " + numvertex + " vertices");
            if (numvertex > threshold) {
             //   int npart = (int) (numvertex / threshold) + 1;
                int npart = 1045;
                numpart = npart;
                idpower = (int) Math.pow(10, (int) (Math.log10(npart)) + 1);
            //    divideGate(fileName, npart);
                //Partition that each vertex belongs (start from 1)
                int[] npartition = new int[numvertex];
                //Number of vertices in each partition
                partvertex = new int[npart];
                for (int i = 0; i < npart; i++) {
                    partvertex[i] = 0;
                }
                File resFile = new File(fileName + ".part." + npart);
                BufferedInputStream bin;
                try {
                    bin = new BufferedInputStream(new FileInputStream(resFile));
                    BufferedReader br = new BufferedReader(new InputStreamReader(bin));
                    String strLine;
                    int intL;
                    int index = 0;
                    while ((strLine = br.readLine()) != null) {
                        intL = Integer.parseInt(strLine);
                        npartition[index] = intL + 1;
                        partvertex[intL]++;
                        index++;
                    }
                    bin.close();
                    br.close();
                    System.out.println("...Read result file");
                    partitioned = new Vector[npart][];
                    for (int i = 0; i < npart; i++) {
                        partitioned[i] = new Vector[partvertex[i]];
                        for (int j = 0; j < partitioned[i].length; j++) {
                            partitioned[i][j] = new Vector<Integer>();
                        }
                        System.out.println("...Finish partition["+i+"]");
                    }
                    System.out.println("...Initialize partitioned[][]");
                    //Convert to list of files for partitioned graph

                    bin = new BufferedInputStream(new FileInputStream(fl));
                    br = new BufferedReader(new InputStreamReader(bin));
                    strLine = br.readLine();
                    int nodeid = 1;
                    int adjid = 0;
                    //StringBuffer sb = new StringBuffer();
                    //StringBuffer boundv = new StringBuffer();
                    while ((strLine = br.readLine()) != null) {
                        //Current' start from 0
                        int current = npartition[nodeid - 1] - 1;
                        int loc = 0;
                        for (int i = 0; i < partitioned[current].length; i++) {
                            if (partitioned[current][i].size() == 0) {
                                loc = i;
                                break;
                            }
                        }
                        partitioned[current][loc].add(nodeid);
                        String[] sscan = strLine.trim().split("\\s");
                        int realdegreecount = sscan.length;
                        //For border graph & connectivity
                        HashSet<Integer> conngroup = new HashSet<Integer>();
                        conngroup.add(npartition[nodeid - 1]);
                        for (int i = 0; i < realdegreecount; i++) {
                            adjid = Integer.parseInt(sscan[i]);
                            if (npartition[adjid - 1] == current + 1) {
                                partitioned[current][loc].add(adjid);
                            } else { //For border graph
                                int tmpBDId = findBorderGraphID(npartition[nodeid - 1], npartition[adjid - 1]);
                                conngroup.add(tmpBDId);
                                BorderGraph tmpBorder = borders.get(tmpBDId);
                                if (tmpBorder == null) {
                                    tmpBorder = new BorderGraph(tmpBDId);
                                    tmpBorder.addEdge(nodeid, adjid);
                                    tmpBorder.setDegree(nodeid, realdegreecount);
                                    borders.put(tmpBDId, tmpBorder);
                                } else {
                                    tmpBorder.addEdge(nodeid, adjid);
                                    tmpBorder.setDegree(nodeid, realdegreecount);
                                }
                                Vector<Integer> conngrpv = new Vector<Integer>(conngroup);
                                for (int i1 = 0; i1 < conngrpv.size(); i1++) {
                                    for (int i2 = 0; i2 < conngrpv.size(); i2++) {
                                        if (i1 != i2) {
                                            HashSet<Integer> temp1 = conngrph.get(conngrpv.get(i1));
                                            if (temp1 == null) {
                                                temp1 = new HashSet<Integer>();
                                                temp1.add(conngrpv.get(i2));
                                                conngrph.put(conngrpv.get(i1), temp1);
                                            } else {
                                                temp1.add(conngrpv.get(i2));
                                            }
                                        }
                                    }
                                }
                            }
                        }
                        partitioned[current][loc].add(realdegreecount);
                        nodeid++;
                    }
                    bin.close();
                    br.close();
                    System.out.println("...Finish reading partitioned[][]&others");
                    constructPartitionedGraph();
                    System.out.println("...Finish construct partitioned graphs");
                    constructBorderGraph();
                    System.out.println("...Finish construct border graphs");
                    constructConnectivityGraph(fileName, conngrph);
                    System.out.println("...FINISH");
                } catch (IOException ex) {
                    System.out.println("Exception in getNumOfVertex1:GraphDivide");
                    ex.printStackTrace();
                }
                return false;
            } else {
                return true;
            }
        }

        return true;
    }

    private static int getNumOfVertex1(File fl) {
        if (fl.exists()) {
            BufferedInputStream bin;
            try {
                bin = new BufferedInputStream(new FileInputStream(fl));
                BufferedReader br = new BufferedReader(new InputStreamReader(bin));
                String strLine = br.readLine();
                Scanner temp = new Scanner(strLine);
                bin.close();
                br.close();
                return temp.nextInt();
            } catch (IOException ex) {
                System.out.println("Exception in getNumOfVertex1:GraphDivide");
                ex.printStackTrace();
            }
        }
        return 0;
    }

    /*private static void divideGate(String fileName, int n) {
        try {
            Runtime rt = Runtime.getRuntime();
            Process p = rt.exec("kmetis.exe " + fileName + " " + n);
          //  InputStream in = p.getInputStream();
          //  OutputStream out = p.getOutputStream();
         //   InputStream err = p.getErrorStream();
            Thread.sleep(n * 15);
            p.destroy();
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }*/

    private static void constructBorderGraph() {
        System.out.println("DED1");
        //      File initg = new File(initialDB);
        //     bin = new BufferedInputStream(new FileInputStream(initg));
        //    BufferedReader br = new BufferedReader(new InputStreamReader(bin));
        //      String strLine = br.readLine();
        Iterator<BorderGraph> bdgit = borders.values().iterator();
        BorderGraph tmpbd = null;
        File tmpfl = new File(resFolder + "/border");
        tmpfl.mkdirs();
        while (bdgit.hasNext()) {
            tmpbd = bdgit.next();
            tmpbd.printToFile(resFolder + "/border");
        }
        //For connectivity graph
        System.out.println("DED2");
    }

    private static int findBorderGraphID(int node1, int node2) {
        if (node1 < node2) {
            return node1 * idpower + node2;
        } else {
            return node2 * idpower + node1;
        }
    }

    /**
     * THIS METHOD IS OBSOLETE PLEASE USE THE CLASS IN GRAPHDIVIDE PROJECT
     * @param initDB
     * @param conngrph
     */
    private static void constructConnectivityGraph(String initDB, HashMap<Integer, HashSet<Integer>> conngrph) {
       /* BufferedOutputStream bos1 = null;
        try {
            File fl = new File(resFolder + "/" + initDB + "k-connectivity");
            bos1 = new BufferedOutputStream(new FileOutputStream(fl));
            PrintStream q1 = new PrintStream(bos1);
            Vector<Integer> key = new Vector<Integer>(conngrph.keySet());
            Collections.sort(key);
            for (int i = 0; i < key.size(); i++) {
                int keyint = key.get(i);
                StringBuffer line = new StringBuffer("" + keyint);
                HashSet<Integer> ress = conngrph.get(keyint);
                Vector<Integer> keymap = new Vector<Integer>(ress);
                Collections.sort(keymap);
                for (int j = 0; j < keymap.size(); j++) {
                    line.append(" " + keymap.get(j));
                }
                q1.println(line);
            }
            q1.flush();
            q1.close();
            bos1.close();
        } catch (Exception e) {
            e.printStackTrace();
        }*/
    }

    private static void constructPartitionedGraph() {
        File fout1 = null;

        BufferedOutputStream bos1 = null;

        PrintStream q1 = null;
        for (int i = 0; i < partitioned.length; i++) {
            try {
                fout1 = new File(Integer.toString(i + 1));
                bos1 = new BufferedOutputStream(new FileOutputStream(fout1));
                q1 = new PrintStream(bos1);
                q1.println("p " + partvertex[i]);
                Vector<Integer> boundary = new Vector<Integer>();
                for (int j = 0; j < partitioned[i].length; j++) {
                    StringBuffer sb = new StringBuffer();
                    Iterator<Integer> line = partitioned[i][j].iterator();
                    while (line.hasNext()) {
                        sb.append(line.next() + " ");
                    }
                    q1.println(sb);
                    if ((partitioned[i][j].size() - 2) < partitioned[i][j].lastElement()) {
                        boundary.add(partitioned[i][j].firstElement());
                    }
                }
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < boundary.size(); j++) {
                    sb.append(boundary.elementAt(j) + " ");
                }
                q1.println();
                q1.println(sb);
                q1.flush();
                q1.close();
                bos1.close();
            } catch (IOException ex) {
                Exceptions.printStackTrace(ex);
            }
        }

    }
}
